Goto

Collaborating Authors

 online dr-submodular maximization


Gradient Methods for Online DR-Submodular Maximization with Stochastic Long-Term Constraints

Neural Information Processing Systems

In this paper, we consider the problem of online monotone DR-submodular maximization subject to long-term stochastic constraints. Specifically, at each round t\in [T], after committing an action \mathbf{x}_t, a random reward f_t(\mathbf{x}_t) and an unbiased gradient estimate of the point \widetilde{ abla}f_t(\mathbf{x}_t) (semi-bandit feedback) are revealed. Meanwhile, a budget of g_t(\mathbf{x}_t), which is linear and stochastic, is consumed of its total allotted budget B_T . Moreover, when first-order full-information feedback is available, we propose an algorithm that achieves (1-1/e) -regret of \mathcal{O}(\sqrt{T}) with \mathcal{O}(T {3/4}) constraint violation. These algorithms significantly improve over the state-of-the-art in terms of query complexity.